package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 树中两个节点的最低公共祖先
 *
 * @author yuhushuan
 * @date 2020/7/4 22:51
 */
public class _68_1_CommonParentInTree {
    private static TreeNode getLastCommonParent(TreeNode root, TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            return null;
        }
        if (node1 == node2){
            return node1;
        }
        // 获取每个节点的路径
        List<TreeNode> path1 = new LinkedList<>();
        List<TreeNode> path2 = new LinkedList<>();
        getNodePath(root, node1, path1);
        getNodePath(root, node2, path2);
        return getLastCommonNode(path1, path2);
    }

    private static boolean getNodePath(TreeNode root, TreeNode node, List<TreeNode> path) {
        if (root == node) {
            return true;
        }
        path.add(root);
        boolean found = false;
        if (root.children != null) {
            for (int i = 0; i < root.children.size(); ++i) {
                TreeNode child = root.children.get(i);
                found = getNodePath(child, node, path);
                if (found) {
                    break;
                }
            }
        }
        if (!found) {
            path.remove(path.size() - 1);
        }
        return found;
    }

    private static TreeNode getLastCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
        if (path1.isEmpty() || path2.isEmpty()) {
            return null;
        }

        int index = 0;
        TreeNode lastNode = null;
        while (index < path1.size() && index < path2.size()) {
            TreeNode node1 = path1.get(index);
            TreeNode node2 = path2.get(index);
            if (node1 == node2) {
                lastNode = node1;
            } else {
                break;
            }
            index++;
        }
        return lastNode;
    }

    public static void main(String[] args) {
        test1();
    }

    private static void test1() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
        TreeNode i = new TreeNode('I');
        TreeNode j = new TreeNode('J');

        a.children = new ArrayList<>(2);
        a.children.add(b);
        a.children.add(c);

        b.children = new ArrayList<>(2);
        b.children.add(d);
        b.children.add(e);

        d.children = new ArrayList<>(2);
        d.children.add(f);
        d.children.add(g);

        e.children = new ArrayList<>(3);
        e.children.add(h);
        e.children.add(i);
        e.children.add(j);

        print(a, f, h);
        print(a, f, g);
        print(a, f, f);
    }

    private static void print(TreeNode root, TreeNode node1, TreeNode node2) {
        System.out.println(node1.value + " 和 " + node2.value + " 的最低公共祖先为：");
        TreeNode commonParent = getLastCommonParent(root, node1, node2);
        if (commonParent == null) {
            System.out.println("null");
        } else {
            System.out.println(commonParent.value);
        }
        System.out.println();
    }
}
